# 在每个树行中找最大值： https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        """
            直接层序遍历，找到每层的最大值即可
        """
        if not root: return []

        rst = []
        queue = deque(); queue.append(root)
        while queue:
            n = len(queue)
            max_row = -2 ** 31
            for i in range(n):
                node = queue.popleft()
                max_row = max(max_row, node.val)

                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)

            rst.append(max_row)
        
        return rst
